Decision trees are commonly used in decision analyses to reach a goal that satisfy one or more conditions. As an example, a decision tree may be used to improve the state of a system from the current state to a desired state of the system by navigating through the decision tree by making decisions along the decision tree. In this example, a metric that represents the state of the system may be used to navigate the decision tree from a root node on the decision tree to a final node on the decision tree, including any intervening nodes on the decision tree.
One technique to navigate a decision tree is by using a greedy algorithm to select nodes on the decision tree with the highest or lowest value for an attribute of interest among possible nodes. Specifically, at each parent node on the decision tree, the greedy algorithm selects the child node of that parent node that has the highest or lowest value for the attribute with respect to all the child nodes of the parent node. For the selected child node, the process is repeated until a certain termination condition is met.
When there is only one attribute being considered in a decision tree (one-dimensional decision tree), the use of a greedy algorithm to traverse the decision tree is fairly straight-forward. However, when there are multiple attributes being considered in a decision tree (multi-dimensional decision tree), the use of a greedy algorithm to traverse such a decision tree is challenging since a child node of a parent node with the highest or lowest value for a particular attribute may not be the optimal choice for the other attributes.